The present invention relates generally to data routing systems, and more particularly to methods and apparatus for efficiently routing packets through a network.
In packet switched communication systems, a router is a switching device which receives packets containing data or control information on one port, and based on destination information contained within the packet, routes the packet out another port to the destination (or an intermediary destination).
Conventional routers perform this switching function by evaluating header information contained within a first data block in the packet in order to determine the proper output port for a particular packet.
Efficient switching of packets through the router is of paramount concern. Referring now to FIG. 1, a conventional router includes a plurality of input ports 2 each including an input buffer (memory) 4, a switching device 6 and a plurality of output ports 8.
Data packets received at an input port 2 are stored at least temporarily, in input buffer 4 while destination information associated with each packet is decoded to determine the appropriate switching through the switching device 6. The size of input buffer 4 is based in part on the speed with which the destination information may be decoded. If the decoding process takes too long as compared to the rate at which packets are received, large sized memory elements may be required or packets may be dropped.
The transfer of data between components in an electrical device, such as a router, often requires some form of synchronization. Synchronization may be achieved by operating devices on the same clock signal, or by providing clocking signals along with each data transfer. Data transfers between subsystems (e.g., between an input port 2 and input buffer 4 or between the input buffer 4 and switching device 6) within a router may be synchronous, source synchronous, asynchronous or isochronous.
Two subsystems in electrical device are characterized as synchronous when each makes use of a common clock signal, for example, to clock logic gates. To be synchronous, both the frequency and phase of the common clock signal at the respective subsystem is the same. Accordingly, where the clock signal is generated externally, delays in reaching each of the subsystems must be matched to maintain the phase relationship.
Conversely, two subsystems are characterized as asynchronous when each uses independent clock signals.
Source synchronous communications are characterized by the transfer of a clock signal along with a data signal when communicating between subsystems. The first subsystem operates in accordance with a first clock signal. Data passed between the first subsystem and a second subsystem is accompanied with a clock signal. The clock that accompanies the data may be the first clock signal or may be derived from the first clock signal. The second subsystem uses this clock signal to process (clock in) the received data into the second subsystem.
Two subsystems are characterized as isochronous when both subsystems use a clock having the same frequency but not necessarily the same phase. The clocks may be externally generated (outside the respective subsystems) but are not required to be delay matched.
The transfer of data through a router often requires the use of source synchronous communication links. Source synchronous communication links include clock and data signals to allow the various components of the router to control the flow of information through the device. However, the use of source synchronous communication links increases the bandwidth required to transfer data between the components.
In general, in one aspect, the invention provides a synchronization circuit for synchronizing components operating isochronously that are coupled by independent links. The synchronization circuit includes a first and second buffer, each including an input port coupled to an external link, an output port, a read pointer and a write pointer. The read pointer indicates a next location in a respective buffer to be read in transferring data out on the output port. The write pointer indicates a next location in the respective buffer to be written when receiving data on the input port and is configured to automatically increment upon receipt of a first data bit on a respective external link.
A trigger circuit is coupled to each link for receiving external trigger signals. Each external trigger signal is included along with data transmitted on the link and indicates when data is present on a respective link.
A counter is coupled to the trigger circuit. The counter includes a trigger input and a predefined delay period. After receipt of a first of the external trigger signals on the trigger input, the counter is operable to output a read enable signal to each of the read pointers after the delay period has expired.
Aspects of the invention include numerous features. The data transmitted over a data portion of the link is the trigger signal.
In another aspect, the invention provides a method for synchronizing components operating isochronously that are coupled by independent links. The method includes providing a synchronization signal from a first component to a plurality of second components through independent first links. Upon detection of the synchronization signal at a respective second component, an acknowledgment signal is returned from each of the second components to the first component through one of a like plurality of second links. When all the acknowledgment signals have been returned, the transmission of the synchronization signal from the first component to the plurality of second components is terminated. Upon detecting the termination of the synchronization signal at each second component, data transfer on the second links is initialized.
Aspects of the invention include numerous features. The first component can be a switch in a router and the second components are input ports for receiving data from a network.
Among the advantages of the invention are one or more of the following. Synchronization of different subsystems is realized without requiring a synchronous interconnect. Multiple subsystems can be synchronized to one common subsystem. Synchronization can be achieved using in-band data so that no additional interconnects are required. Mutual synchronization between two subsystems can be realized (from a first system to a second system and then from the second system back to the first system). Synchronization of multiple subsystems can be achieved out of order. A dependent synchronization of a first subsystem to a second subsystem can be achieved even if the synchronization of the second subsystem to the first subsystem is required to be performed first.
Other advantages and features will be apparent from the following description and claims.